package lcr;

import java.util.Deque;
import java.util.LinkedList;

public class Test0025 {
}

class Solution0025_1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ans = new ListNode();
        Deque<ListNode> deque1 = new LinkedList<>();
        Deque<ListNode> deque2 = new LinkedList<>();
        while (l1!=null||l2!=null){
            if (l1!=null){
                deque1.offer(l1);
                l1=l1.next;
            }

            if (l2!=null){
                deque2.offer(l2);
                l2=l2.next;
            }
        }

        boolean flag = deque1.size() > deque2.size();
        ans.next= flag ?deque1.peek():deque2.peek();

        int yu = 0;
        while (!deque1.isEmpty()||!deque2.isEmpty()){
            ListNode now = flag ? deque1.peekLast() : deque2.peekLast();
            int val1 = !deque1.isEmpty()?deque1.pollLast().val : 0;
            int val2 = !deque2.isEmpty()?deque2.pollLast().val : 0;
            int sum = val2 + val1 + yu;
            now.val = sum%10;
            yu = sum/10;
        }
        if (yu==1) {
            ListNode node = new ListNode(1);
            node.next = ans.next;
            ans.next = node;
        }

        return ans.next;
    }
}